Dynamic Programming

Dynamic Programming (DP) is a method used to solve complex problems by breaking them down into smaller overlapping subproblems and solving each subproblem only once.

The results of these subproblems are stored (memoized or tabulated) and reused, which saves computation time.

In short: DP = Recursion + Memoization/Tabulation

• Focus on final optimal solution
• Solve complex problem by breaking them down into simpler sub-problem
• Solve each sub-problem only once and store the result

Key Characteristics of DP Problems

A problem can be solved using Dynamic Programming if it has:

Optimal Substructure

• The solution of a big problem can be built using solutions of its smaller subproblems.
• Example: In shortest path problems, the shortest path from A → C via B is built from shortest(A→B) + shortest(B→C).

Overlapping Subproblems

• The same subproblems are solved multiple times.
• Example: In Fibonacci, to calculate fib(5), we need fib(4) and fib(3). But fib(4) also needs fib(3).
• Without DP → fib(3) is recalculated many times. With DP → we store it.

Two Main Approaches of DP

Top-Down (Memoization)

• Use recursion.
• Store results of subproblems in a map/array (so they aren’t recomputed).
• Small set of input
• Solve overlapping sub-problem
• Example: fib(5) → compute recursively, but remember results.

Bottom-Up (Tabulation)

• Iterative approach.
• Store in array
• Build solutions for smaller subproblems first, then use them to build the final answer.
• Large set of input
• Do not overlap
• Usually more sxpace-efficient.

Example Problem of Dynamic Programming

Naive Recursive Solution (Exponential Time)

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

• Time Complexity: O(2^n)
• Space Complexity: O(n)
• Because many values (like fib(3)) are recalculated multiple times.

DP with Memoization (Top-Down)

int fibMemo(int n, vector<int> &dp) {
    if (n <= 1) return n;

    if (dp[n] != -1) return dp[n];  // already computed

    return dp[n] = fibMemo(n-1, dp) + fibMemo(n-2, dp);
}

int main() {
    int n = 10;
    vector<int> dp(n+1, -1);
    cout << "Fibonacci(" << n << ") = " << fibMemo(n, dp);
}

• Stores results in dp array.
• Time Complexity: O(n)
• Space Complexity: O(n) (stack + dp array).

DP with Tabulation (Bottom-Up)

int fibTab(int n) {
    vector<int> dp(n+1, 0);
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];

    return dp[n];
}

• Builds solution iteratively.
• Time Complexity: O(n)
• Space Complexity: O(n) (but can be optimized to O(1) by storing only last two values).

General Template

1D DP Template

int solveDP(int n) {
    vector<int> dp(n + 1, 0); // DP array initialized to zero

    // Base case value, adjust as needed
    dp[0] = 0;

    // Loop through the problem
    for (int i = 1; i <= n; ++i) {
        // Example transition (adjust this according to the problem)
        dp[i] = min(dp[i - 1] + 1, dp[i - 2] + 2);  // Example DP relation
    }

    return dp[n];  // Return the result (e.g., final value in dp array)
}

• To get the count/min cost/max cost of dp relation you can use:

  dp[i] = cost[i] + min(dp[i - 1] + 1, dp[i - 2] + 2);

• To get the path you can add:

  parent[i] = (dp[i - 2] < dp[i - 1]) ? i - 2 : i - 1;

  • Then add the following outside the loop

    int lastStep = (dp[n - 2] < dp[n - 1]) ? n - 2 : n - 1;
    int minCost = dp[lastStep];
    
    // Reconstruct the path
    vector<int> path;
    int curr = lastStep;
    while (curr != -1) {
        path.push_back(curr);
        curr = parent[curr];
    }
    reverse(path.begin(), path.end());
    
    cout << "Minimum cost: " << minCost << "\nPath: ";
    for (int step : path) {
        cout << step << " ";
    }
    cout << endl;

2D DP Template

int solveDP2D(int m, int n) {
    // Create a 2D DP array (m+1 x n+1) initialized to 0
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // Base case setup
    for (int i = 0; i <= m; ++i) {
        dp[i][0] = 0;  // Adjust based on the problem
    }
    for (int j = 0; j <= n; ++j) {
        dp[0][j] = 0;  // Adjust based on the problem
    }

    // Fill the DP table
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            // Example DP relation (adjust based on the problem)
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + 1;  // Modify this according to problem logic
        }
    }

    return dp[m][n];  // Return the result (e.g., final cell in the dp table)
}